package com.example.lcpractice.array;


/**
 * 在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列
 * 都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一
 * 个整数，判断数组中是否含有该整数
 * <p>
 * 0 1 ... n
 * ——————————> 0
 * | 1
 * | ...
 * |
 * \|/m
 */
public class FindNum2DimenArr {

    public static void main(String[] args) {
        int[][] a = {{1, 3, 5}, {27, 35, 44}, {45, 50, 51}};
        int t = 44;
        final boolean b = fun2(a, t);
        System.out.println(b);
    }

    /**
     * 时间：o(mn),空间: o(1)
     *
     * @param arr
     * @param target
     * @return
     */
    public static boolean fun1(int[][] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        int row = 0;
        int column = arr[0].length - 1;
        while (row < arr.length && column >= 0) {
            if (arr[row][column] == target) {
                return true;
            } else if (arr[row][column] > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }


    public static boolean fun2(int[][] arr, int target) {
        if (arr == null || arr.length == 0) {
            return false;
        }
        // 第0格子
        int left = 0;
        // 第m*n-1格子
        int right = arr.length * arr[0].length - 1;
        //列数
        int col = arr[0].length;

        while (left <= right) {
            int mid = (left + right) / 2;
            // 中间数/列数为第mid / col行,中间数%列数为行起止第 mid % col 个
            int value = arr[mid / col][mid % col];
            if (value == target) {
                return true;
            } else if (value < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return false;
    }

}
